package 牛客网_N.查找_递归_排序_贪心.container_with_most_water;

import java.util.Scanner;

/**
 * 
Given n non-negative integers a1 , a2 , ..., an , where 
each represents a point at coordinate (i, ai ). n vertical 
lines are drawn such that the two endpoints of line i is 
at (i, ai ) and (i, 0). Find two lines, which together 
with x-axis forms a container, such that the container 
contains the most water.
Note: You may not slant the container.
 * @author x
 * @summary
 */
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		String str = in.nextLine();
		String[] dataStr = str.split(" ");
		int[] height = new int[dataStr.length];
		for(int i = 0; i < dataStr.length; i++){
			height[i] = Integer.parseInt(dataStr[i]);
		}
		System.out.println(maxArea2(height));
	}
	/**
	 * 暴力遍历，取得所有，排序，取得最大
	 * @param height
	 * @return
	 */
	public static int maxArea(int[] height) {
		int[] Area = new int[(height.length)*(height.length-1)/2];
		int k = 0;
		for(int i = 0; i < height.length; i++){
			for(int j = 0; j < i; j++){
				Area[k] = (i-j)*Math.min(height[i], height[j]);
				k++;
			}
		}
		
		for(int i = 0; i <= k-1; i++){
			for(int j = 0; j < k-1; j++){
				if(Area[j]>Area[j+1]){
					int temp = Area[j];
					Area[j] = Area[j+1];
					Area[j+1] = temp;
				}
			}
		}
		return Area[k-1];
	}
	/**
	 * 暴力遍历，取得最大
	 * @param height
	 * @return
	 */
	public static int maxArea2(int[] height){
		int max = 0;
		int area = 0;
		for(int i = 0; i < height.length; i++){
			for(int j = 0; j < i; j++){
				area = (i-j)*Math.min(height[i], height[j]);
				if(area>max) max = area;
			}
		}
		return max;
	}
	/**
	 * 贪心算法，从两侧往中间取，保留大的边长，小的边长往中间位移，
	 * 正方形面积，获得的最小边越大，面积越大
	 * @param height
	 * @return
	 */
	public static int maxArea3(int[] height){
		int left = 0;
		int right = height.length-1;
		int max = 0;
		int area = 0;
		while(left < right){
			area = (right-left)*Math.min(height[right], height[left]);
			if(area > max) max = area;
			if(height[left] < height[right]){
				left++;	
			}else{
				right--;
			}
		}
		return max;
	}
	
}
